/**
 * 跳台阶问题
 * 题目描述:
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法?
 * 分析:
 * 设到第n阶总共有f(n)种跳法，而且想跳到第n阶只有两种可能，要么从第n-1阶跳一阶到达，要么从第n-2阶跳两阶到达，所以递推式为f(n)=f(n-1)+f(n-2)。
 * 特殊情况为，n=0的时候跳法为0；n=1时，跳法为1；n=2时，跳法为2
 */

 //递归方法
 function jump(n){
     if (n<1) {
        return 0
     }
     else if (n === 1) {
         return 1
     }
     else if (n === 2) {
         return 2
     }
     else{
         return jump(n-1)+jump(n-2)
     }
 }
console.log(jump(9))
 //非递归方法
function jumpFloor(number) {
    //n >= 3 才能满足斐波那契数列规则
    if (number < 1){
        return 0;
    }
    else if (number === 1){
        return 1;
    }
    else if (number === 2){
        return 2;
    }
    var s1 = 1;
    var s2 = 2;
    var res = 0;
    for (var i = 3; i <= number; i++) {
        res = s1 + s2; //f(n) = f(n-2) + f(n-1)
        s1 = s2; //令f(n-2) = f(n-1)继续算法
        s2 = res; //令f(n-1) = f(n)继续算法
    }
    return res;
}

/**
 * 变态跳台阶问题
 * 题目描述：
 * 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
 * 分析：
 * 对于n阶变态跳，公式有以下特点：
 * f(n) = f(n-1)+f(n-2)+...+f(1); （1）
 * f(n-1) = f(n-2)+f(n-3)+...+f(1); （2）
 * （1）-（2），即f(n) = 2f(n-1)，可以看出n阶变态跳的结果，实际是一个等比数列，也就是f(n) = 2^(n-1)
 */

 //递归方法
function SuperJump(number) {
    if (number < 1)
        return 0;
    if (number === 1)
        return 1;
    return 2 * SuperJump(number - 1)
}

/**
 * 超级变态跳台阶问题
 * 题目：
 * 假设有n级台阶，每次最多允许跨m步（m<=n），那么有多少种跨越方式？
 * 分析：
 * 自顶向下分析规律，发现f(n,m) = f(n-1,m)+f(n-2,m)+...+f(n-m,m)
 * 当m=2时，就是一个斐波那契数列；
 * 当n=m时，就上上述变态跳台阶问题
 */

//递归方法
function SuperSuperJump(n, m) {
    var count = 0;
    if (n == 0) {
        return 1;
    }
    if (n >= m) {
        for (var i = 1; i <= m; i++) {
            count += SuperSuperJump(n - i, m);
        }
    } else {
        count += SuperSuperJump(n, n);
    }
    return count;
}
